//
// Created by Administrator on 2021/5/31.
//
/*

在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点 逐行 依次按“之” 字形进行标记。

如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标记；

而偶数行（即，第二行、第四行、第六行……）中，按从右到左的顺序进行标记。



给你树上某一个节点的标号 label，请你返回从根节点到该标号为 label 节点的路径，该路径是由途经的节点标号所组成的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-in-zigzag-labelled-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
#include <vector>
#include <iostream>
#include <cmath>

using namespace std;

class Solution {
public:
    vector<int> pathInZigZagTree(int label) {
        int level = log(label) / log(2) + 1; // 计算层数
        vector<int> path(level);
        while (label) {
            path[level-1] = label;
            label = pow(2, level) - 1 - label + pow(2, level - 1);  // 计算该节点的对称点。比如 4 的对称点是 7，7 的对称点是 4， 5 对应 6
            // 对称点的父节点
            label >>= 1;
            // 上移一层
            level--;
        }
        return path;
    }
};


int main() {
    Solution sol;
    auto ans = sol.pathInZigZagTree(14);
    for (auto &x:ans) cout << x << endl;
    return 0;
}